package hot100;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.stream.Collectors;

public class DecodeString {
    public String decodeString(String s) {
        char[] chars = s.toCharArray();
        Deque<String> stack = new ArrayDeque<>();
        StringBuilder sbNum = new StringBuilder();
        StringBuilder sbStr = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= '0' && chars[i] <= '9') {
                if (sbStr.length() > 0) {
                    String curStr = sbStr.toString();
                    sbStr.delete(0,sbStr.length());
                    stack.addLast(curStr);
                }
                sbNum.append(chars[i]);
            } else if (chars[i] == '[') {
                //当前数目入栈
                String curNumStr = sbNum.toString();
                sbNum.delete(0,sbNum.length());
                stack.addLast(curNumStr);
                stack.addLast("" + chars[i]);
            } else if (chars[i] >= 'a' && chars[i] <= 'z') {
                sbStr.append(chars[i]);
            } else if (chars[i] == ']') {
                while (!"[".equals(stack.getLast())) {
                    sbStr.insert(0,stack.removeLast());
                }
                //移除左括号
                stack.removeLast();
                //当前字符串入栈
                String curStr = sbStr.toString();
                sbStr.delete(0,sbStr.length());
                String curNumStr = stack.removeLast();
                int curNum = Integer.parseInt(curNumStr);
                for (int j = 0; j < curNum; j++) {
                    sbStr.append(curStr);
                }
                curStr = sbStr.toString();
                sbStr.delete(0,sbStr.length());
                stack.addLast(curStr);
            }
        }

        if (sbStr.length() != 0) {
            String curStr = sbStr.toString();
            sbStr.delete(0,sbStr.length());
            stack.addLast(curStr);
        }

        String decoded = stack.stream().collect(Collectors.joining());

        return decoded;
    }

    @Test
    public void test() {
        String s = "abc3[cd]xyz";
        System.out.println(decodeString(s));
    }
}
